#define _CRT_SECURE_NO_WARNINGS 1


//https://leetcode.cn/problems/symmetric-tree/
//bool isSameTree(TreeNode* p, TreeNode* q) {
//    if (p == NULL && q == NULL)
//    {
//        return true;
//    }
//    if (p == NULL || q == NULL)
//    {
//        return false;
//    }
//    if (p->val != q->val)
//    {
//        return false;
//    }
//    if (isSameTree(p->left, q->right) && isSameTree(p->right, q->left))
//        return true;
//    else {
//        return false;
//    }
//}
//
//class Solution {
//public:
//    bool isSymmetric(TreeNode* root) {
//        return isSameTree(root->left, root->right);
//    }
//};


//https://leetcode.cn/problems/binary-tree-preorder-traversal/
//typedef struct TreeNode TreeNode;
//int TreeSize(TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    return 1 + TreeSize(root->left) + TreeSize(root->right);
//}
//
//void _preorderTraversal(TreeNode* root, int* returnArr, int* pi)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    returnArr[(*pi)++] = root->val;
//    _preorderTraversal(root->left, returnArr, pi);
//    _preorderTraversal(root->right, returnArr, pi);
//}
//
//int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//    *returnSize = TreeSize(root);
//    int* returnArr = (int*)malloc(sizeof(int) * (*returnSize));
//    int i = 0;
//    _preorderTraversal(root, returnArr, &i);
//    return returnArr;
//}
//
//https://leetcode.cn/problems/binary-tree-inorder-traversal/
//typedef struct TreeNode TreeNode;
//int TreeSize(TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    return 1 + TreeSize(root->left) + TreeSize(root->right);
//}
//
//void _inorderTraversal(TreeNode* root, int* returnArr, int* pi)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    _inorderTraversal(root->left, returnArr, pi);
//    returnArr[(*pi)++] = root->val;
//    _inorderTraversal(root->right, returnArr, pi);
//}
//
//int* inorderTraversal(struct TreeNode* root, int* returnSize) {
//    *returnSize = TreeSize(root);
//    int* returnArr = (int*)malloc(sizeof(int) * (*returnSize));
//    int i = 0;
//    _inorderTraversal(root, returnArr, &i);
//    return returnArr;
//}
//
//https://leetcode.cn/problems/subtree-of-another-tree/description/
//class Solution {
//public:
//    bool check(TreeNode* o, TreeNode* t) {
//        if (!o && !t) {
//            return true;
//        }
//        if ((o && !t) || (!o && t) || (o->val != t->val)) {
//            return false;
//        }
//        return check(o->left, t->left) && check(o->right, t->right);
//    }
//
//    bool dfs(TreeNode* o, TreeNode* t) {
//        if (!o) {
//            return false;
//        }
//        return check(o, t) || dfs(o->left, t) || dfs(o->right, t);
//    }
//
//    bool isSubtree(TreeNode* s, TreeNode* t) {
//        return dfs(s, t);
//    }
//};
//
//
//https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
//typedef struct TreeNode TreeNode;
//int TreeSize(TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    return 1 + TreeSize(root->left) + TreeSize(root->right);
//}
//
//void _postorderTraversal(TreeNode* root, int* returnArr, int* pi)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    _postorderTraversal(root->left, returnArr, pi);
//    _postorderTraversal(root->right, returnArr, pi);
//    returnArr[(*pi)++] = root->val;
//}
//
//int* postorderTraversal(struct TreeNode* root, int* returnSize) {
//    *returnSize = TreeSize(root);
//    int* returnArr = (int*)malloc(sizeof(int) * (*returnSize));
//    int i = 0;
//    _postorderTraversal(root, returnArr, &i);
//    return returnArr;
//}


